/**
 * @author gao
 * @date 2025/6/21 20:39
 */

public class AVLTree {
    static class TreeNode {
        int val; // 节点的值
        TreeNode left; // 左孩子节点
        TreeNode right; // 右孩子节点
        TreeNode parent; // 父节点
        int bf; //平衡因子

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;//根节点

    /**
     * AVL树的插入
     * @param val
     * @return
     */
    public boolean insert (int val) {
        // 如果根节点为空，则创建一个新的节点作为根节点
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;

        while (cur != null) {
            // 如果当前节点的值小于要插入的值，则向右子树遍历
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            // 如果当前节点的值等于要插入的值，则返回false
            } else if (cur.val == val) {
                return false;
            // 如果当前节点的值大于要插入的值，则向左子树遍历
            } else {
                parent = cur;
                cur = cur.left;
            }
        }

        // 如果要插入的值大于父节点的值，则将新节点插入到父节点的右子树
        if (parent.val < val) {
            parent.right = node;
        // 如果要插入的值小于父节点的值，则将新节点插入到父节点的左子树
        } else {
            parent.left = node;
        }

        node.parent = parent;
        cur = node;

        // 调节平衡因子
        while (parent != null) {
            if (cur == parent.right) {
                parent.bf++;
            } else {
                parent.bf--;
            }

            // 说明已经平衡了
            if (parent.bf == 0) {
                break;
            // 当前子树平衡，但整棵树不平衡，继续向上调整
            } else if (parent.bf == 1 || parent.bf == -1) {
                cur = parent;
                parent = cur.parent;
            } else {
                if (parent.bf == 2) {//右树高，需要降低右子树的高度
                    if (cur.bf == 1) {
                        rotateLeft(parent);
                    } else if (cur.bf == -1) {
                        rotateRL(parent);
                    }
                } else if (parent.bf == -2) {//左树高，需要降低左子树的高度
                    if (cur.bf == 1) {
                        rotateLR(parent);
                    } else if (cur.bf == -1) {
                        // 进行右旋
                        rotateRight(parent);
                    }
                }
                // 执行完上述代码，说明平衡了
                break;
            }
        }
        return true;
    }

    /**
     * 右左双旋
     * @param parent
     */
    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        // 右旋右子节点
        rotateRight(parent.right);
        // 左旋父节点
        rotateLeft(parent);

        // 如果右子节点的左子节点的平衡因子为1
        if (bf == 1) {
            subR.bf = 0;
            subRL.bf = 0;
            parent.bf = -1;
        // 如果右子节点的左子节点的平衡因子为-1
        } else if (bf == -1) {
            subR.bf = 0;
            subRL.bf = 1;
            parent.bf = 0;
        }
    }

    /**
     * 左右双旋
     * @param parent
     */
    private void rotateLR(TreeNode parent) {
        // 获取左子节点
        TreeNode subL = parent.left;
        // 获取左子节点的右子节点
        TreeNode subLR = subL.right;
        // 获取右子节点的平衡因子
        int bf = subLR.bf;

        // 左旋左子节点
        rotateLeft(parent.left);
        // 右旋父节点
        rotateRight(parent);

        // 如果右子节点的平衡因子为-1
        if (bf == -1) {
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        // 如果右子节点的平衡因子为1
        } else if (bf == 1) {
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
    }

    /**
     * 右单旋
     * @param parent
     */
    private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        // 将parent节点的左子节点设置为subLR
        parent.left = subLR;
        // 将subL节点的右子节点设置为parent
        subL.right = parent;
        //没有subLR节点
        if (subLR != null) {
            subLR.parent = parent;
        }
        // 将subLR节点的父节点设置为parent
        // 获取parent节点的父节点
        TreeNode pParent = parent.parent;
        // 将parent节点的父节点设置为subL
        parent.parent = subL;

        // 如果parent节点是根节点，则将subL节点设置为根节点
        if (parent == root) {
            root = subL;
            root.parent = null;
        } else {
            // 如果parent节点是其父节点的左子节点，则将subL节点设置为parent节点的父节点的左子节点
            if (pParent.left == parent) {
                pParent.left = subL;
            // 如果parent节点是其父节点的右子节点，则将subL节点设置为parent节点的父节点的右子节点
            } else if (pParent.right == parent) {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.bf = 0;
        parent.bf = 0;
    }

    /**
     * 左单旋
     * @param parent
     */
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;
        subR.left = parent;
        if (subRL != null) {
            subRL.parent = parent;
        }

        TreeNode pParent = parent.parent;
        parent.parent = subR;

        if (root == parent) {
            root = subR;
            root.parent = null;
        } else {
            if (pParent.left == parent) {
                pParent.left = subR;
            } else if (pParent.right == parent) {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        subR.bf = 0;
        parent.bf = 0;
    }

    /**
     * 验证是否为二叉搜索树
     * @param root
     */
    public void InOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        InOrder(root.left);
        System.out.println(root.val + " ");
        InOrder(root.right);
    }

    /**
     * 计算二叉树高度
     * @param root
     * @return
     */
    public int Height(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 递归计算左子树的高度
        int leftH = Height(root.left);
        // 递归计算右子树的高度
        int rightH = Height(root.right);

        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    /**
     * 验证是否为AVL树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        int leftH = Height(root.left);
        int rightH = Height(root.right);

        if (rightH - leftH != root.bf) {
            System.out.println("平衡因子异常");
            return false;
        }

        return Math.abs(leftH - rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
}